In a modern computer network, or simply a network, routers route data between various networks by forwarding the packets (“packets”) to the next router on a path to the packet destination. Typically, a router employs a forwarding table to enable such forwarding decisions. When a link between routers goes down, the routers can use alternate routes for data forwarding. Furthermore, one or more of the routers updates the forwarding table to reflect that the link is down.
FIG. 1 (Prior Art) is a block diagram illustrating one embodiment of a network. In FIG. 1, routers 102A-D couple to networks 104A-D, respectively. Router 102A-D acts as a junction between two of more networks 104A-D via links 106A-F. Links 106A-F represent connections and/or coupling between respective routers 102A-D. For example and by way of illustration, router 102A couples to routers 102B-D via links 106A, E, and D, respectively. Furthermore, router 102B couples to routers 102C-D via links 106B and F, respectively, while router 102C couples to router 102D via link 106C. The coupling of routers 102A-D via links 106A-F allows devices in one network to access other devices in another network. For example and by way of illustration, devices in network 104A can access other devices in network 104B via router with links 106A-F.
Typically, routers 102A-D employ routing algorithms that are used to determine which links 106A-F are available to access network 104A-D. Routing algorithms discover routes to other network as well exchanging known routes with other routers 102A-D. Typically routing algorithms use a forwarding information table that designates which routes are used to access a given network 104A-D. Routing algorithms are well known in the art and typically depend on a routing protocol. A routing protocol is set of rules used by routers to determine the most appropriate path(s) into which they should forward packets towards their intended destinations. Example of routing protocols known in the art are Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), Border Gateway Protocol (BGP), Routing Information Protocol (RIP), etc.
One problem that typically occurs is that one of links 106A-F will sometimes go down, meaning that network communication across the downed link is not available. When one of link 106A-F goes down, router 102A-D detects that link down using one of a various methods known in the art associated with the routing protocol being used by router 102A-D. For example and by way of illustration, if router 102A-D is using OSPF for its routing protocol, router 102A-D detects a down link by determining if three consecutive hello packet are not received over a period of time. In one embodiment, this period of time is thirty seconds. However, the problem with this approach is that each routing protocol has a different mechanism for link down detection and link down detection may take minutes.
FIG. 2 (Prior Art) is a block diagram illustrating various routing protocols using Bidirectional Forwarding Detection (BFD) to detect faults between two forwarding engines. BFD is a routing protocol independent mechanism used to detect a link 106A-F down between two routers 102A-D. BFD provides a low-overhead detection of link down for various types of links (Ethernet, tunnels, virtual circuits, etc.). BFD establishes a session between two endpoints on a link. For example and by way of illustration, BFD would establish a session for link 106A between routers 102A-B. BFD does not discover the links, but typically relies on a routing protocol such as OSPF or IS-IS to bootstrap BFD with the link and endpoint information.
Once BFD is running, an overlaying routing protocol gets link events from BFD. As shown in FIG. 2, different routing protocols can receive the link events from BFD. In FIG. 2, routing protocols 202A-N rely on BFD 204 for link events 206. In addition, routing protocols, such OSPF 202A or IS-IS 202B can send BFD session bootstrap information 208 to BFD.
BFD detects link downs very quickly, on the order of tens of milliseconds. Once a link is detected, a BFD-Down event is sent to the controlling routing protocol. The overlaying routing protocol receives the event and treats the link as down. Nonetheless, because BFD is routing protocol independent and thus not part of any routing protocol standard, how the routing protocol treats the BFD-Down event is implementation dependent. For example and by way of illustration, current implementations for OSPF treat BFD-Down event by taking the OSPF state for that link to the DOWN state. One problem with this implementation is that typically the data structure associated with the neighboring router is deleted. This deprives the router's BFD process of monitoring the link between the router and neighboring router because the underneath transport no longer maintains the corresponding BFD session. Furthermore, because BFD detects link downs very quickly, BFD session can go up and down quickly, leading to link flapping.